/**
* Created with CLion.
* User:Lenovo
* Date:2023-05-22
* Time:2:07
* Description:图的存储
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct Node
{
    int data;
    struct Node *next;
} Node;

typedef struct Edge
{
    int to;
    int next;
    int w;
} Edge;

void Adj()
{
    int adj[5][5] = { 0 };
    adj[0][1] = 1;
    adj[0][3] = 1;
    adj[1][2] = 1;
    adj[1][3] = 1;
    adj[2][3] = 1;
    adj[2][4] = 1;
    adj[4][3] = 1;
    adj[4][0] = 1;

}

void AddList(Node *pHead, int x)
{
    if (pHead == NULL)
    {
        pHead = (Node *)malloc(sizeof(Node));
        pHead -> next = NULL;
    }

    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode -> next = NULL;
    newNode -> data = x;
    while (pHead -> next)
    {
        pHead = pHead -> next;
    }
    pHead -> next = newNode;
}

void AdjList()
{
    Node *adj[100] = {NULL};// 开大一点，相当于数据极限
    AddList(adj[0], 1);
    AddList(adj[0], 3);
    AddList(adj[1], 2);
    AddList(adj[1], 3);
    AddList(adj[2], 3);
    AddList(adj[2], 4);
    AddList(adj[4], 0);
    AddList(adj[4], 0);
}

void add(Edge edge,int u, int v, int w, int *count, int *head)
{
    // u 起点，v 终点，w 边权，count 下标计数
    edge.w = w;
    edge.to = v;
    edge.next = head[u];// 这个边的前一个边是 head[u] 中存着的数 - 起点相同
    head[u] = *count++;// head[u] 更新：u 所指向的第一条边下标就是现在的 count
}

void SFList()
{
    Edge edge[100] = { 0 };
    int head[5];
    for (int i = 0; i < 5; i++)
    {
        head[i] = -1;
    }
    int count = 0;
    add(edge[count], 0, 1, 1, &count, head);
    add(edge[count], 0, 3, 1, &count, head);
    add(edge[count], 1, 2, 1, &count, head);
    add(edge[count], 1, 3, 1, &count, head);
    add(edge[count], 2, 3, 1, &count, head);
    add(edge[count], 2, 4, 1, &count, head);
    add(edge[count], 4, 0, 1, &count, head);
    add(edge[count], 4, 3, 1, &count, head);

    /* edge[0].next = -1，edge[1].next = 0，因为这两条边的起点都是 0
     * 遍历的时候从 head[0] 开始，也就是从 1 开始
     * 所以在顺序上是倒序遍历，但是对结果没有影响
     */
}

int main()
{
    // 主要分为三种方法：邻接矩阵，邻接表，(链式)前向星
    // 假设要表示的图如下所示(有向图)：
    /*         1
     *       / | \
     *     2 - 3 - 0
     *       \ | /
     *         4
     * 0 -> 1，0 -> 3，1 -> 2，1 -> 3，2 -> 3，2 -> 4，4 -> 3，4 -> 0
     */

    // 1.邻接矩阵(Adjacency Matrix)
    {
        // 能够直观的表示邻接矩阵的边(存储的是顶点之间的相邻关系)
        // 建立二维数组 adj[u][v]，二维数组的行数 u 等于列数 v 等于节点个数
        // adj[u][v] 存在两种情况 - 为 0 表示节点 u 到节点 v 之间不存在边，为 1 表示节点 u 到节点 v 之间存在边
        // 当存在边权的情况下，adj[u][v] 也可以存储边权
        // 优点是直观，好理解，缺点是对于稀疏图来说会有大量的空间浪费

        // 代码示例：
        Adj();
    }

    // 2.邻接表(Adjacency List)
    {
        // 结构类似于哈希表，采用了顺序存储和链式存储相结合的方式来存放数据
        // 采用了结构体指针数组 Node，Node[i] 表示第 i 个节点存放的数据的头指针
        // Node[i] 后面所连接的链表的数据域 data 表示节点的标号，指针域指向下一个节点，这个节点表示 i 指向另一个编号为 data 的节点，如果没有节点则置空
        // 简单来说，假设 i = 0，Node[0] -> data1 表示 0 指向了 data1，Node[0] -> next -> data2 表示 0 同时指向了 data2
        // 邻接表的链表部分没有顺序，意味着邻接表不唯一，0 可以先指向 data1 在指向 data2，也可以反过来

        // 代码示例：
        AdjList();
    }

    // 3.链式前向星(鬼知道这东西英文是什么，为什么要叫这个名)
    {
        // 真是奇怪的名字呢(划掉)
        // 使用到两个东西：第一个是用结构体定义的边(结构体数组)，第二个是 head 数组，head[i] 用来保存以 i 为起点的第一条边在 struct 数组里的下标
        // 定义结构体 Edge 和 head 数组：见上
        // edge 的下标已经和节点没有关系了，只是单纯表示数组里面有多少个数据
        // edge[i].to 表示第 i 条边的终点，edge[i].next 表示第 i 条边的上一条边的下标(方便遍历)，edge[i].w 表示第 i 条边的边权
        // 有关 head 数组的部分解释将在代码示例里实现

        // 代码示例：
        SFList();
    }

    return 0;
}